ПОДХОД К ПРОГРАММИРОВАНИЮ НЕДЕТЕРМИНИРОВАННЫХ ИГР
(Часть II: СПЕЦИАЛЬНЫЕ ЭВРИСТИКИ И ПРИМЕРЫ) 

Мельников Борис Феликсович, доктор физико-математических наук, профессор, кафедра прикладной математики и информатики, Тольяттинский филиал Самарского государственного университета (Россия, г. Тольятти, ул. Юбилейная, 31Г), B.Melnikov@tltsu.ru
Мельникова Елена Анатольевна, кандидат физико-математических наук, доцент, кафедра прикладной математики и информатики, Тольяттинский филиал Самарского государственного университета (Россия, г. Тольятти, ул. Юбилейная, 31Г), E.Melnikova@tltsu.ru
Радионов Алексей Николаевич, кандидат технических наук, доцент, кафедра прикладной математики и информатики, Тольяттинский государственный университет (Россия, г. Тольятти, ул. Белорусская, 14), alx.radionov@gmail.com

004.8.023, 004.83 

Актуальность и цели. Создание интеллектуальных компьютерных игр является одним из основных направлений искусственного интеллекта. Кроме того, компьютерные игры предоставляют мощный арсенал разнообразных средств, используемых для обучения. Классическим метод для программирования детерминированных игр для двух лиц с полной информацией – это минимаксный алгоритм. При программировании недетерминированных игр неприменимы стандартные методы, развитые для детерминированных игр. Цель работы: разработать алгоритмы для недетеминированных игр, основанные на обработке модифицированного дерева поиска игры.
Материалы и методы. Разработаны эвристики для упорядочивания вершин в недетерминированном дереве перебора, которые сокращают время обработки узлов дерева и, следовательно, позволяют с большой вероятностью получать оценку исследуемой игровой позиции, близкую к оптимальной. Также рассмотрена возможность одновременного применения недетерминированного дерева перебора и нейронных сетей. В статье приведены примеры работы предложенных алгоритмов для построения конкретных оценок вершин (игровых позиций) различных уровней в недетерминированном дереве перебора. Для практического применения описываемых эвристик в игровых программах необходима оценочная функция позиций. В статье описаны способы ее построения и самообучения. В примерах работы алгоритмов значения оценок выбираются таким образом, чтобы примеры, несмотря на их малый объем, были бы интересными.
Результаты. Разработанные авторами алгоритмы реализованы в компьютерных игровых программах, они также находят свое применение не только непосредственно в недетерминированных играх, но и в других задачах дискретной оптимизации.
Выводы. Применение разработанных авторами эвристик позволяет повысить эффективность алгоритмов для программирования недетерминированных игр: уменьшить время работы и объем используемой памяти, улучшить качество игры. 

алгоритмизация, недетерминированные игры, модифицированное дерево поиска. 

1. Кормен, Т. Алгоритмы – построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. – М. : Вильямс, 2005. – 1296 с.
2. Мельников, Б. Мультиэвристический подход к задачам дискретной оптимизации / Б. Мельников // Кибернетика и системный анализ. НАН Украины. – 2006. – № 3. – С. 32–42.
3. Melnikov, B. Some special heuristics for discrete optimization problems / B. Melnikov, A. Radionov, V. Gumayunov // 8th International Conference on Enterprise Information Systems. – Paphos, Cyprus, 2006. – Р. 360–364.
4. Melnikov, B. Discrete optimization problems – some new heuristic approaches / B. Melnikov // 8th International Conference on High Performance Computing and Grid in Asia Pacific Region, IEEE Computer Society Press Ed. – Beijing, China, 2005. – Р. 73–80.
5. Баумгертнер, С. Мультиэвристический подход к проблеме звeздно-высотной минимизации недетерминированных конечных автоматов / С. Баумгертнер, Б. Мельников // Вестник Воронежского государственного университета. Сер. Сист. анализ и инф. технологии. – 2010. – № 1. – С. 5–7.
6. Адельсон-Вельский, Г. Программирование игр / Г. Адельсон-Вельский, В. Арлазаров, М. Донской. – М. : Наука, 1978. – 255 с.
7. Tesauro, G. Temporal difference learning and TD-Gammon / G. Tesauro // Commun. ACM. – 1995. – Vol. 38, № 3. – P. 58–68.
8. Мельников, Б. Эвристики в программировании недетерминированных игр / Б. Мельников // Программирование. Известия РАН. – 2001. – № 5. – С. 63–80.